package com.ankicoo.practice.daily;

import org.apache.ibatis.annotations.Param;

import java.util.*;

/**
 * Description: 862. 和至少为 K 的最短子数组
 *  给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
 * @author : QCYANG
 * @date : 2022/10/26 17:31
 */
public class LC862 {
    private static Integer size;
    public static int shortestSubArray(int[] nums, int k) {
        int sum = 0;
        Deque<Integer> result = new ArrayDeque<>();
        size = nums.length+1;

        //队列 一进一出 记录总内容
        for (int num : nums) {
            if (result.size()>0&&num<0){
                sum = sum + num;
                sum = addLast(result,num ,sum);

                int calSum = 0;
                for (Integer sig : result) {
                    calSum = calSum + sig;
                }
                System.out.println(sum +"------"+calSum);
                System.out.println(result);
                System.out.println("----------------------");
            }else{
                result.addLast(num);
                sum = sum + num;
                sum = popFirst(k,sum,result);
                if (size==1){
                    break;
                }
                int calSum = 0;
                for (Integer sig : result) {
                    calSum = calSum + sig;
                }
                System.out.println(sum +"------"+calSum);
                System.out.println(result);
                System.out.println("----------------------");
            }

        }


        return size==nums.length+1?-1:size;
    }

    public static Integer addLast(Deque<Integer> result , Integer num,Integer sum){
        if (result.size()>0&&num<0){
            int temp = result.getLast() + num;
            result.removeLast();
            if (temp>=0){
                result.addLast(temp);
            }else{
                if(result.size()==0){
                    sum = 0;
                }
                sum = addLast(result,temp,sum);
            }
            result.addLast(0);
        }
        return sum;
    }

    public static Integer popFirst(Integer k, Integer sum , Deque<Integer> result ){
        if(result.getFirst()<=0){
            sum = sum - result.getFirst();
            result.removeFirst();
        }
        if(sum>=k){
            size = Math.min(result.size(), size);
            if(size ==1 ){
                 return sum;
            }
            if ((sum - result.getFirst())>=k){
                sum = sum - result.getFirst();
                result.removeFirst();
                sum = popFirst(k,sum,result);
            }
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {-36,10,-28,-42,17,83,87,79,51,-26,33,53,63,61,76,34,57,68,1,-30};
        int k =  484;
        int finalSize = shortestSubArray(nums, k);
        System.out.println(finalSize);
    }
}
